<HTML>
<HEAD>
  <TITLE>Complexity</TITLE>
</HEAD>
<BODY BGCOLOR="FFFFFF">

<TABLE WIDTH="100%" BGCOLOR="EEEEFF"><TR><TD>
  <A HREF="index.html">cppreference.com</A> -&gt; Complexity
</TD></TR></TABLE>

<H3>Complexity</H3>

<P>There are different measurements of the speed of any given algorithm.  Given an
input size of <strong>N</strong>, they can be described as follows:
</P>

<TABLE>
  <TR> 
    <TH>Name</TH>
    <TH>Speed</TH>
    <TH>Description</TH>
  <TR>
  <TR BGCOLOR="EEEEFF">
    <TD>exponential time</TD>
    <TD>slow</TD>
    <TD>takes an amount of time proportional to a constant raised to the 
      <STRONG>N</STRONG>th power (K^<STRONG>N</STRONG>)</TD>
  <TR>
  <TR> 
    <TD>polynomial time</TD>
    <TD>fast</TD>
    <TD>takes an amount of time proportional to <STRONG>N</STRONG> raised 
      to some constant power (<STRONG>N</STRONG>^K)</TD>
  <TR>
  <TR BGCOLOR="EEEEFF"> 
    <TD>linear time</TD>
    <TD>faster</TD>
    <TD>takes an amount of time directly proportional to <STRONG>N</STRONG> 
      (K * <STRONG>N</STRONG>)</TD>
  <TR>
  <TR> 
    <TD>logarithmic time</TD>
    <TD>much faster</TD>
    <TD>takes an amount of time proportional to the logarithm of
      <STRONG>N</STRONG> (log(<STRONG>N</STRONG>))</TD>
  <TR>
  <TR BGCOLOR="EEEEFF"> 
    <TD>constant time</TD>
    <TD>fastest</TD>
    <TD>takes a fixed amount of time, no matter how large the input is (K)</TD>
  <TR>
</TABLE>

</BODY>
</HTML>
